
// Definition for singly-linked list.
struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution
{
public:
    // 找分界点
    ListNode *get_mid(ListNode *start)
    {
        ListNode *s = start;
        ListNode *f = start;
        while (f && f->next && f->next->next)
        {
            f = f->next;
            f = f->next;
            s = s->next;
        }
        ListNode *ret = s->next;
        s->next = nullptr;
        return ret;
    }
    // 递归空间复杂度O(log(n))
    ListNode *marge_sort(ListNode *start)
    {
        if (!(start->next))
            return start;
        // 获取分界点
        ListNode *r = get_mid(start);
        ListNode *l = start;
        // 分治两边
        l = marge_sort(l);
        r = marge_sort(r);
        // 归并 不使用辅助空间 打断插入(链表插入不需要挪动数据)
        ListNode *head = new ListNode;
        ListNode *cur = head;
        while (l || r)
        {
            if (!r || (l && l->val < r->val))
            {
                cur->next = l;
                l = l->next;
            }
            else
            {
                cur->next = r;
                r = r->next;
            }
            cur = cur->next;
        }
        return head->next;
    }
    ListNode *sortList(ListNode *head)
    {
        if (!head)
            return nullptr;
        return marge_sort(head);
    }
};
// 非递归 n*log(n) O(1)
#include<utility>
using namespace std;
class Solution
{
public:
    pair<ListNode *, ListNode *> marge(ListNode *left, ListNode *right)
    {
        ListNode *temp_head = new ListNode(0);
        ListNode *cur = temp_head;
        while (left || right)
        {
            if (!right || left && left->val < right->val)
            {
                cur->next = left;
                left = left->next;
            }
            else
            {
                cur->next = right;
                right = right->next;
            }
            cur = cur->next;
        }
        return {temp_head->next, cur};
    }
    ListNode *sortList(ListNode *head)
    {
        int size = 0;
        for (ListNode *temp = head; temp; temp = temp->next)
            size++;
        ListNode *new_head = new ListNode(0, head);
        ListNode *cur = new_head->next;
        ListNode *new_cur = new_head;
        int len = 1;
        while (len <= size + 1 / 2)
        {
            cur = new_head->next;
            new_cur = new_head;
            while (cur)
            {
                ListNode *left = cur;
                ListNode *left_end = left;
                for (int i = 0; i < len - 1; i++)
                {
                    if (!left_end->next)
                        break;
                    left_end = left_end->next;
                }
                ListNode *right = left_end->next;
                ListNode *right_end = right;
                ListNode *next = right_end;
                left_end->next = nullptr;
                if (right_end)
                {
                    for (int i = 0; i < len - 1; i++)
                    {
                        if (!right_end->next)
                            break;
                        right_end = right_end->next;
                    }
                    next = right_end->next;
                    right_end->next = nullptr;
                }
                auto marge_res = marge(left, right);
                new_cur->next = marge_res.first;
                new_cur = marge_res.second;
                cur = next;
            }
            len *= 2;
        }
        return new_head->next;
    }
};